package com.benben.springSecurity.weiwei;

import java.util.ArrayList;
import java.util.List;

//分治算法
//1，分解：按运算符分成左右两部分，分别求解
//2，解决：实现一个递归函数，输入算式，返回算式解
//3，合并：根据运算符合并左右两部分的解，得出最终解
public class MaxScorePath {
    public List<Integer> diffWaysToCompute(String input) {
        return partition(input);
    }
    public List<Integer> partition(String input) {
        List<Integer> result = new ArrayList<>();
        if(!input.contains("+") && !input.contains("-") && !input.contains("*")){
            result.add(Integer.valueOf(input));
        }
        for(int i=0;i<input.length();i++){
            if(input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*'){
                for (Integer left : partition(input.substring(0,i))) {
                    for (Integer right : partition(input.substring(i+1))){
                        if(input.charAt(i) == '+'){
                            result.add(left+right);
                        } else if(input.charAt(i) == '-'){
                            result.add(left - right);
                        } else if(input.charAt(i) == '*'){
                            result.add(left * right);
                        }
                    }
                }
            }
        }
        return result;
    }
}
